/****************************************************
File Name:  quickSFile.cpp
Author:     Animesh Sharma
Date:       11/2005
Description:    Source code for Quicksort Algorithm - Array based Implementation(Project 3 cs352)
Submission Date: 1st Dec 2005
Project Due Date: 1st Dec 2005
****************************************************/


#include <iostream>
#include <string>
#include <stdlib.h>

using namespace std;

void QuickSort (char** wordList, int indexLow, int indexHigh);
int Partition (char** wordList, int indexLow, int indexHigh);


int main ()
{
	char inputFile[512], outputFile[512];
	printf ("Enter the Input File: ");
	gets (inputFile);
	printf ("Enter the Name of Output File: ");
	gets (outputFile);

	const int arraySizeIncrease = 16;
	int arraySize = arraySizeIncrease, wordCount = 0;
	char** wordListArray = new char* [arraySize];
	char wordSize [512];
	FILE* fileInputStream = fopen (inputFile, "rt");
	while (fgets (wordSize, 512, fileInputStream))
	{
		char* wordCheck = wordSize;
		while (*wordCheck != '\0')
		{
			if (*wordCheck == '\n' && *(wordCheck + 1) == '\0')
				*wordCheck = '\0';
			wordCheck++;
		}

		wordListArray[wordCount] = new char [strlen (wordSize) + 1];
		strcpy (wordListArray[wordCount], wordSize);
		wordCount = wordCount + 1;
		if (wordCount % arraySizeIncrease == 0)
		{
			char** szPrev = wordListArray;
			arraySize += arraySizeIncrease;
			wordListArray = new char* [arraySize];
			memcpy (wordListArray, szPrev, wordCount * sizeof(char*));
			delete szPrev;
		}
	}
	fclose (fileInputStream);

	QuickSort (wordListArray, 0, wordCount - 1);

	fileInputStream = fopen (outputFile, "wt");
	for (int nIndex = 0; nIndex < wordCount; nIndex++)
	{
		fprintf (fileInputStream, "%s\n", wordListArray[nIndex]);
	}
	fclose (fileInputStream);

	for (int nIndexN = 0; nIndexN < wordCount; nIndexN++)
	{
		delete wordListArray[nIndexN];
	}
	delete wordListArray;
	wordListArray = NULL;

	printf ("\nOutput file Written.\n\n");
	return 0;
}

void QuickSort (char** wordList, int indexLow, int indexHigh)
{
	if (indexLow < indexHigh)
	{
		int nSplit = Partition (wordList, indexLow, indexHigh);
		QuickSort (wordList, indexLow, nSplit - 1);
		QuickSort (wordList, nSplit + 1, indexHigh);
	}
}

int Partition (char** wordList, int indexLow, int indexHigh)
{
	int nLeft = indexLow + 1;
	char* szPivot = wordList[indexLow];
	int nRight = indexHigh;

	char* szSwap;
	while (nLeft <= nRight)
	{
		while (nLeft <= nRight && strcmp (wordList[nLeft], szPivot) <= 0)
			nLeft = nLeft + 1;
		while (nLeft <= nRight && strcmp (wordList[nRight], szPivot) > 0)
			nRight = nRight - 1;
		if (nLeft < nRight)
		{
			szSwap = wordList[nLeft];
			wordList[nLeft] = wordList[nRight];
			wordList[nRight] = szSwap;
			nLeft = nLeft + 1;
			nRight = nRight - 1;
		}
	}
	szSwap = wordList[indexLow];
	wordList[indexLow] = wordList[nRight];
	wordList[nRight] = szSwap;
	return nRight;
}
